#ifndef CONVEXHULL_H
#define CONVEXHULL_H

#include <QPointF>
#include <QStack>
#include "Collision.h"

class ConvexHull {
public:
	~ConvexHull() {}

	static ConvexHull* create(QPointF* points, int size) {
		ConvexHull* hull = new ConvexHull();
		QPointF* stack = new QPointF[size];
		QPointF* sortPoints = new QPointF[size];
		for (int i = 0;i < size;i++) {
			sortPoints[i] = points[i];
		}
		if (size <= 2) {
			hull->points = sortPoints;
			hull->size = size;
			return hull;
		}
		for (int i = 0;i < size - 1;i++) {
			for (int j = i + 1;j < size;j++) {
				if (sortPoints[i].x() > sortPoints[j].x() ? true : (sortPoints[i].x() == sortPoints[j].x() ? (sortPoints[i].y() > sortPoints[j].y() ? true : false) : false)) {
					QPointF temp = sortPoints[i];
					sortPoints[i] = sortPoints[j];
					sortPoints[j] = temp;
				}
			}
		}
		int top = 0;
		for (int i = 0;i < size;i++) {
			while (top > 1 && ConvexHull::cross(stack[top - 2], stack[top - 1], sortPoints[i]) <= 0) {
				top--;
			}
			stack[top++] = sortPoints[i];
		}
		int t = top;
		for (int i = size - 2;i >= 0;i--) {
			while (top > t && ConvexHull::cross(stack[top - 2], stack[top - 1], sortPoints[i]) <= 0) {
				top--;
			}
			stack[top++] = sortPoints[i];
		}
		hull->points = stack;
		hull->size = top - 1;
		return hull;
	}

	AABB* toAABB() {
		AABB* aabb = new AABB();
		aabb->setPoints(this->points);
		aabb->setPointSize(this->size);
		return aabb;
	}

	static float cross(QPointF a, QPointF b, QPointF c) {
		return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x());
	}
private:
	QPointF* points;
	int size = 0;
};

#endif